\section{Preliminaries}\label{sec:preliminaries}

\subsection{Memristor and Memristor-Based Memory}
The theoretical concept of memristor is predicted by Prof. Leon Chua in
1960's~\cite{memristor:chua}. The memristor is predicted as the fourth
basic element that imposes the relationship between the flux ($\varphi$)
and the charge ($q$) as: $d\varphi=Mdq$. The variable $M$ is the
memristance of a memristor. From this definition, we can get that:
\begin{eqnarray}
\label{equ:definition}
M(q)=\frac{d\varphi/dt}{dq/dt}=V/I.
\end{eqnarray}
As shown in this equation, the memristance has the same unit as resistance,
and the memristor can be considered as a two-terminal element in which the
magnetic flux between the terminals is a function of the amount of electric
charge that passes through the device. The first experimental implementation
of the memristor was demonstrated by HP Labs in 2008~\cite{memristor:missing}
based on a metal-insulator-metal (MIM) structure. As shown in
Figure~\ref{fig:structures}(a), the memristor built by HP Labs has a
two-terminal, two-layer structure. The top and the bottom electrodes are
nanowires made by $Pt$. Two layers of titanium dioxide are sandwiched between
these two electrodes in a crossbar architecture. By applying an external
voltage across the device, the memristor can switch between two stable
states: ON state with low resistance and OFF state with high resistance. A
positive voltage above a specific threshold will switch the device into the
OFF state (RESET operation) and a negative voltage of the same magnitude
toggles it to its ON state (SET operation). The
memristive switching behaviors have been observed in many MIM nanodevice with
different materials.

The switching mechanism of the MIM nanodevice is still unknown. One of the
most possible reasons is that different mechanisms may affect the
nanodevice simultaneously and it is hard to distinguish the effect of
certain mechanism. In addition, even a certain mechanism may affect the
device with different materials at very different degrees, which further
exacerbates the possibility to extract a universal model for all of the
MIM nanodevices. However, the switching mechanism of $TiO_2$ based MIM
nanodevice, namely memristor, has been well
studied~\cite{memristor:mechanism}. Therefore, in this paper, we mainly
focus on the memristor-based ReRAM. However, the concept and methodology
can be easily applied to other MIM device based ReRAM designs.

%The lower layer of $TiO_2$ has a perfect 2:1 ratio of oxygen to titanium. By contrast, the upper layer is lack of a small amount of oxygen, and can be denoted as $TiO_{2-x}$. As we know, the perfect titanium dioxide itself is insulating. However, the oxygen deficiency in the $TiO_{2-x}$ will
%significantly increase the conductivity of the titanium dioxide.
%Therefore, the memristor cell can be modeled as two series-connected
%resistors, which is shown in Figure.\ref{fig:model}(a). In this figure,
%the resistance of the pure $TiO_2$ is indicated as $R_H$ and the
%resistance of $TiO_{2-x}$ is $R_L$. By applying an external biased voltage across the $TiO_2$ thin film, the oxygen vacancies will drift from the low potential part to the high potential part, which will changes the ratio of high resistant part to the low resistance part of the memristor and
%therefore changes the overall resistance of the memristor.

%*******************************Edit by Yang_Xiao**************************
%Another class of memristor, spintronic memristor, is proposed by
%Wang~\cite{memristor:Spin_Wang}~\cite{memristor:Spin_Wang_2}. Via their
%examples, the authors deem the memristive effect is a general property
%among the spintronic devices. Different from the memristor proposed by HP
%Labs, the resistance of spintronic devices depends on their own
%magnetization state which is a cumulative result of electron spin
%excitations. Three examples of spintronic device manifesting the
%memristive phenomenon are presented: (1) Magnetic tunneling junction (MTJ)
%structure: the resistance of this example is determined by the angle
%($\theta$) between the magnetizations of the free layer and reference
%layer while the value of the angle is the result from the integral of
%current. (2) Single thin-film structure with fixed thickness but variable
%width: the resistance is a function of the position of the domain wall, an
%boundary separating two magnetic domains. The moving velocity of this
%wall, the derivative of the domain wall position, relates to the current
%density, which makes the position a function of the integral of
%current/voltage. (3). Long spin-valve structure: a two layers structure
%that the bottom one is a reference layer and the upper one is a free layer
%containing two magnetic domains pointing to opposite direction separated
%by domain wall. Note that, in this case, the resistance equation is very
%similar to the HP Lab's model. In this paper, the magnetic tunneling
%junction(MTJ) based spintronic memristor is used for its simple structure.

\begin{figure}
\centering
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.45\textwidth]{./figures/curv.pdf}\\
    \vspace{-5pt}
  \caption{Structures and IV curve of memristor cell. (a) MIM structure of the $TiO_2$ memristor cell. (b) I-V curve of the memristor with ON/OFF states.}\label{fig:structures}
  \vspace{-10pt}
\end{figure}


%One layer is stoichiometric $TiO_2$, of which the ratio of oxygen to
%titanium is exactly 2 to 1, leaving it in its natural state as an
%insulator. The adjacent layer is lack of a small amount of oxygen, which
%is called oxygen-deficient titanium dioxide $TiO_{2-x}$, making it a
%semiconductor which is relatively high in conductivity. By applying a bias
%voltage across the crossbar junction, oxygen vacancies drift from the
%doped layer to the undoped layer, increasing the portion of
%oxygen-deficient titanium dioxide with the whole resistance decreased,
%thereby turning on the memory switch. Likewise, by changing current
%direction, oxygen vacancies can be driven to migrate back into the doped
%layer, thus turning the memory switch off. After the demonstration of HP
%Labs' memristor, the memristive effects in spintronic systems were also
%studied and the three spintronic memristors were proposed by Wang
%~\cite{memristor:Spin_Wang}.
%
Memristor-based memory has been firstly proposed by
Ho~\cite{memristor:pengli}. There are two possible memory organizations
for memristor-based memory: \begin{enumerate}

\item \noindent\textbf{Memory Array Structure.} In the memristor-based
    memory array, the conventional memory cell is substituted by the
    memristor where the access device remains to be the MOSFET. This is illustrated
    in Figure~\ref{fig:arch0}(a). In this structure, since each memristor
    cell has to be accompanied with a MOSFET access device whose size is much
    larger than the memristor, the memory cell size is mainly dominated by MOSFET
    access device rather than the actual memristor, and therefore the
    area efficiency is affected.

\item \noindent\textbf{Cross-Point Structure.}
    The cross-point array is a
    more area-efficient structure for the memristor-based
    ReRAM~\cite{memristor:Cong}. In the cross-point array, the only item
    at each crossing point is the memristor cell. Therefore, the area of
    the array is significantly reduced since the large MOSFET access part
    is removed without considering memory peripheral. For the cross-point
    structure, a two-step writing methodology, ERASE-before-RESET, is used
    to prevent the unintended writing. In read operation two ways are
    exhibited for preventing a read failure: the first is to supply the
    same voltage to the unselected row and selected column. In this way,
    only the data on the select row is read from the selected column. The
    disadvantage of this method is the voltage drop on the crossing points
    of the unselected row and the selected column may not be ideal zero
    because of variations, and this imposes a limitation on the array
    size. The second way is a two-step write operation. The disturbance
    current of the partial selected cell on the selected column will be
    read out beforehand as a background current. Later the total current,
    comprised of both partial selected cell and full selected cell, will
    be read out. The state of the selected cell can then be determined by
    computing the difference between the total current and background
    current.
\end{enumerate}
%The array size constraint is solved base on the $V/2$ biasing scheme, a
%method based on the relationship of the current of half selected cell and
%the driver current is used to find the maximum number of rows and columns
%for cross point array. The challenges of writing and reading are solved
%separately.
%
%In write operation, two-step writing methodology is used if both 0's and
%1's are need to write to memory since we need to prevent the absolute
%value of voltage drop on the partial selected cell being larger than $V$
%for the possibility of unintended writing. The ERASE-before-RESET is
%chosen for energy reason. In read operation two ways are exhibited for
%preventing a read failure: the first is to supply the same voltage to the
%unselected row and selected column. In this way, only the data on the
%select row is read from the selected column. The disadvantage of this
%method is the voltage drop on the crossing points of the unselected row
%and the selected column may not be ideal zero because of variations and
%result in the limitation of the array size. The second one is a two-step
%operation like writing. The disturbance current of the partial selected
%cell on the selected column will be read out beforehand as a background
%current. Later the total current, comprised of both partial selected cell
%and full selected cell, will be read out. The state of the selected cell
%then can be determined by computing the difference between the total
%current and background current.

\begin{figure}
\centering
  % Requires \usepackage{graphicx}
  \includegraphics[width=0.5\textwidth]{./figures/memristor_conv_array.pdf}\\
  \vspace{-5pt}
  \caption{Structures of memory array of memristor. (a) The schematic view of MOS-accessed array. (b) The schematic view of cross-point memory array. (WL=wordline, BL=bitline, SL=sourceline) }\label{fig:arch0}
  \vspace{-15pt}
\end{figure}


%*******************************Edit by Yang_Xiao******************************************************

\subsection{Error Correcting Code}
The error correcting code (ECC) is widely studied in the information theory. The basic concept of ECC is to use additional data (or parity data)
to store enough information for error detection and correction. ECC has been
used in diverse areas during the past decades, such as the Internet,
deep-space telecommunication and the civil communication servers. ECC has
also been applied in the computer architecture area to improve the
reliability of data storage and computing. For example, in hard drives every
sector contains a number of extra bits for error correcting and recovery
(such as CRC32). Besides, the Reed Solomon (RS) codes are widely used in CDs
to correct errors which are generated by scratches.

Hamming codes are a special class of ECC with $n=2^m-1$ and $k=2^m-m-1$ for $m>=3$. These code have a minimum distance of 3 and can detect and correct a single-bit error or detect two-bit error(but Hamming code can not distinguish these two kinds of error during the decoding). The most popular ECC code in computer memory systems is SEC-DED Hamming code, which is a class of truncated Hamming codes. The truncation increases the minimum distance of the Hamming code from 3 to 4, ensuring that the SEC-DED Hamming can detect and correct a single-bit error and detect two-bit error at the same time. Besides the Hamming code, a more powerful class of ECC, BCH code, has also been proposed in the memory systems such as Flash storage and optical media. Different from the Hamming codes, the BCH codes can provide multi-bit error correction.

Traditional DRAM memory also employed ECC to correct transient soft errors. The ECC used in DRAM is the SEC-DED. Therefore, data that has
more than 3 bits error at the same block is insensible to the systems. It is reasonable for DRAM systems because the soft error rate (SER) for DRAM is quite low and the probability that more than two errors occur in the same block is extremely low. However, if a system has a correlated error
pattern, stronger ECC is required.

In fact, for the ideal memristor-based memory, ECC is not necessary because the memristor is different from the DRAM cell and is resistant to soft errors induced by cosmic rays. However, it has been shown that~\cite{memristor:logarithm}, under the impact of process variability, the physical characteristics of memristor cells may deviate from the design requirement and therefore bring in some undesirable errors\cite{memristor:dimin}\cite{memristor:ASPDAC}. In order to mitigate the impact of the process variation, more reliable programming method is required for the memristor-based memory, which is energy inefficient. Therefore, energy-aware ECC which is specially designed for memristor-based memories, is vitally necessary.
